This invention relates generally to the testing of very large scale integration (VLSI) circuits using test patterns (also know as test vectors) that are applied to scan paths within circuits. More particularly, this invention relates to the generation of test patterns for finding random pattern-resistant faults within a VLSI circuit.
Most modern digital integrated circuits incorporate a variety of design for testability (DFT) features such as scan path or partial scan to make their testing and diagnosis possible. In test mode, all flip-flops in a full scan design are configured into one or more shift registers called scan paths, with each of the flip flops being a cell of the scan path. This solution provides an excellent controllability and observability of all memory elements in a circuit. Arbitrary test patterns can be applied to the combinational part of the circuit, and its test responses can be observed on the scan cells by a simple shift operation.
The test patterns can be computed and applied in several different ways. One popular approach is to use automatic test pattern generation (ATPG) to compute the test patterns and apply them with a testing device to the circuit under test. The testing device stores the test patterns explicitly, applies them to the circuit under test, and compares the circuit responses to ideal responses to determine if the circuit operates correctly. The ATPG tools available today can generate test patterns with a high degree of fault coverage (i.e., the percentage of possible circuit faults that are detectable) for VLSI circuits. But the storage needed for the large number of test patterns required can easily exceed the testing device""s storage capacity.
An alternative to ATPG is Built-In Self Test (BIST), which does not store test patterns. The general state of the art in this area is summarized by V. D. Agrawal, C. K. Kime, and K. K. Saluja, in xe2x80x9cA Tutorial on Built-In Self Test, Part 1: Principles,xe2x80x9d IEEE Design and Test of Computers, March 1993, pp. 73-82, which is incorporated herein by reference. In BIST, hardware within the circuit under test generates test patterns, evaluates test responses, and controls the test application. One popular BIST architecture uses scan paths as a basic DFT technique, Pseudorandom Pattern Generators (PRPG) as sources of test patterns, and multiple input signature registers (MISR) as compactors of test responses. The PRPG uses a linear feedback shift register (LFSR) or a cellular automata (CA) as a source of test patterns capable of generating sequences of millions of test pattern without repetition. The PRPG generates pseudorandom test patterns that are shifted to the circuit under test through scan and boundary scan. Once a test pattern is shifted, the circuit is reconfigured into normal system mode for at least one clock cycle to load the response back to the scan path. At this point the responses are shifted out, while at the same time a new test pattern is shifted in. The test responses obtained from shifting of many scan chains are compacted into a signature. The control circuitry provides the necessary signals which control the test application, determine the number of test patterns applied, the length of the shift operation, etc. The BIST control circuitry on an integrated circuit may be connected to and driven by the IEEE 1149.1 TAP controller. In this case it might be possible to load the initial seed of the PRPG, the number of test patterns to be applied, and read the final signature.
It has been found, however, that many real circuits are resistant to pseudorandom pattern testing. A simple example of such a circuit is a 32-input AND gate. A test for stuck-at-0 fault on the output of this AND gate requires that all 32 inputs assume a value 1. A PRPG which generates test patterns with A 50% probability of a logic 1 on each input must generate on average four billion patterns to detect the fault, a prohibitively large number.
One approach to eliminate random pattern resistance is presented by B. H. Seiss, P. M. Trouborst and M. H. Schulz in xe2x80x9cTest Point Insertion for Scan-Based BIST,xe2x80x9d Proceedings of European Test Conference, 1991, pp.253-262, which is incorporated herein by reference. This approach relies on the insertion of control and observation points into the circuit to increase the controllability and observability of critical areas of the circuit so that faults in these areas can be detected by the application of pseudorandom test patterns. The control points are inserted into the circuit as additional gates or additional inputs to gates. They are disabled in the normal mode, and they do not alter the circuit function (though they may affect circuit delay). In test mode, control points are driven by additional scan cells connected to a PRPG.
This approach addresses the problem of random pattern resistance, but it has some disadvantages. First, there is additional circuit area overhead required for the control points, observation points, and the scan cells to drive them. On average one test point requires ten additional gates. Second, since the control points are driven by the additional scan cells, the points must switch at the same rate as any other inputs to the combinational logic. If BIST is to be applied at-speed, these signals have to be routed with the same timing constraints as any other signals in the circuit logic. Third, due to additional switching on the control points, there is an increased power dissipation during test mode.
Another approach is presented by N. Tamarapalli and J. Rajski in xe2x80x9cConstructive Multi-Phase Test Point Insertion for Scan-Based BIST,xe2x80x9d Proceedings of International Test Conference,xe2x80x9d pp. 649-658, 1996, and in U.S. Pat. No. 5,737,340, which are incorporated herein by reference. Multi-phase test point insertion (MTPI) is used to activate the control points in a number of phases. A divide-and-conquer technique partitions the whole test into a number of phases, and a phase decoder circuit activates a subset of control points by applying fixed values for the duration of the phase. The algorithm assigning control points in a given phase targets the faults which remain undetected after the previous phases. The assignments work synergistically to detect the faults while avoiding conflicting assignments, which are activated in different phases. This approach maximizes the fault coverage and minimizes area overhead and power dissipation. It, however, requires that a test point be inserted in every circuit area containing undetected faults. If the area contains very few faults, the returns per insertion increasingly diminish.
For circuits where the insertion of test points is not possible, such as legacy designs, or not desirable due to a possible impact on area performance or design flow, several other techniques have been developed to reduce the amount of test data to store. In weighted random pattern testing, pseudorandom patterns are biased, i.e. the probability of generating logic states 0 and 1 may be different For example, if weighted random patterns are applied to test completely a 32-input AND gate, the optimum probability of value 1 is {fraction (31/32)}, and consequently {fraction (1/32)} for value 0. For those values the average test length of a complete test is approximately 350 patterns, as opposed to four billion for equiprobable patterns. Although the test length is reduced significantly, the method requires storage of weights, i.e., the signal probabilities for each input or scan cell of the circuit. In this example, one set of signal probabilities was used. It has been demonstrated that real circuits require multiple weight sets, in some instances more than a hundred. Each weight set specifies signal probabilities for all inputs of the circuit. It involves up to four bits of data per scan cell. Although this is a significant reduction of data compared to explicit storage of test data, the amount of test data to store is still significant for large circuits. A number of weighted random pattern (WRP) generators are known such as those disclosed in U.S. Pat. Nos. 5,394,405; 5,043,988; 5,297,151; and 4,687,988. However, these WRP generators are significantly more complex than uniform pseudorandom pattern generators, and their use have been restricted to off-chip BIST.
Another weighted testing approach is presented by S. Pateras and J. Rajski in xe2x80x9cCube-Contained Random Patterns and Their Application to the Complete Testing of Synthesized Multi-Level Circuits,xe2x80x9d Proceedings of International Test Conference, pp. 473-482, 1991, which is incorporated herein by reference. In this method the granularity of weights has been reduced to just three: 0%, 100% and 50%. In one part of the test in which test patterns are generated from a single weight set, some inputs assume a constant value of logic 0 (0%), constant values of logic 1 (100%) or pseudorandom signals with equal probability of 0 and 1 (50%). Since only two bits are required per scan cell for each weight set to store, the complexity of the WRP generator is reduced. The method requires more weight sets to compensate for the reduced granularity of signal probabilities.
U.S. Pat. No. 5,323,400, which is incorporated herein by reference, discloses another weighted testing approach in using a scan cell with reduced set weighted random patterns. The scan cell contains a logic gate on its output. The gate is inserted between the conventional scan cell and the combinational logic. There are two different types of scan cells to produce constant values: one type in test mode produces value 0 on its output, another type produces 1. Two other types of scan cells can produce random signals with probability 0.25 and 0.75. This solution implements a single weight set random patterns. Since most real circuits require multiple weights to obtain satisfactory fault coverage, this solution may not guarantee high quality of testing. In addition, each scan cell with this modification introduces one gate delay to the circuit, causing its performance to degrade.
Yet another testing approach is presented by B. Chinaman in xe2x80x9cLFSR-Coded Test Patterns for Scan Designs,xe2x80x9d Proceedings of European Test Conference, pp.237-242, 1991, which is incorporated herein by reference. This approach combines the benefit of pseudorandom and deterministic patterns. Pseudorandom patterns detect a majority of faults, and a ATPG tool targets the remaining random pattern-resistant faults, generating test cubes or partially specified test patterns with unspecified positions. A solver program uses these test cubes to determine the seeds of the PRPG such that when they are loaded to the LFSR and clocked into the circuit, they produce test patterns which agree on all specified positions of the test cubes. This technique does not require any circuit modification other than scan path. It relies on ATPG tool and provides an effective compression technique for deterministically computed incompletely specified test patterns. This technique usually provides as high a fault coverage as the ATPG tool on which it is based. The size of the seed may be much larger than the length of the PRPG. The main drawback of this method is the overhead of a long LFSR and the amount of data (one seed per test pattern).
A method has been proposed by N. Zacharia, J. Rajski and J. Tyszer in xe2x80x9cTwo-dimensional Test Data Decompressor for Multiple Scan designs, xe2x80x9d International Test Conference, 1996, pp. 186-194, which is incorporated herein by reference, where the scan elements can be used to extend the length of the PRPG required for reseeding without incurring significant area overhead. A small number of patterns is sufficient to test all random pattern-resistant faults. Although this method reduces the hardware overhead, the amount of test data to store is still quite significant. For every test cube, there is one seed which has to be stored.
For the reasons given, none of these prior testing approaches effectively detects random pattern-resistant faults as efficiently as may be desired. An objective of the invention, therefore, is to provide a low cost yet efficient method for detecting faults in circuits under test.
The method maintains high fault coverage of a circuit under test while it reduces the amount of test data to store by using clusters of correlated test patterns. A test pattern generator stores only a small number of center test vectors which serve as centers of clusters. The generator applies each center test vector to a circuit under test multiple times. However, every time the center vector is shifted into the circuit, some of its positions are complemented. The cluster may have a number of spheres which correspond to test vectors derived with various diffraction probabilities and computed to maximize fault coverage, minimize the total number of clusters, and reduce the test application time. The method also encodes several partially specified center test vectors in scan path using the polarity between scan cells, scan order and waveform generators controlling scan inputs.
More specifically, a method in accordance with the invention is disclosed for generating multiple weighted test patterns from an initial test pattern. The method comprises copying a multibit initial test pattern from an initial location; generating a set of weighting factor bits; combining the weighting factor bits with the copied initial test pattern bits to form a multibit weighted test pattern; and repeating the copying, generating and combining to form multiple weighted test patterns from the initial test pattern.
Also disclosed is a method for determining a test pattern for detecting faults within a circuit. The method comprises performing a fault simulation of the circuit to identify a list of random pattern-resistant faults therein; generating a set of multi-bit test patterns that detects a desired share of the random pattern-resistant faults; selecting from the set a test pattern that detects a desired number of the random pattern-resistant faults; and filling one or more don""t care bit positions of the selected test pattern with bit values computed from the unselected test patterns to determine the test pattern.